package 中等.二分查找;

import java.util.Arrays;

/**
 * 给你一个整数数组 nums ，其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数 maxOperations 。
 * 你可以进行如下操作至多 maxOperations 次：
 * 选择任意一个袋子，并将袋子里的球分到 2 个新的袋子中，每个袋子里都有 正整数 个球。
 * 比方说，一个袋子里有 5 个球，你可以把它们分到两个新袋子里，分别有 1 个和 4 个球，或者分别有 2 个和 3 个球。
 * 你的开销是单个袋子里球数目的 最大值 ，你想要 最小化 开销。
 * 请你返回进行上述操作后的最小开销。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/minimum-limit-of-balls-in-a-bag
 */
public class 袋子里最少数目的球_1760 {

    public static void main(String[] args) {

        System.out.println(minimumSize(new int[]{7, 17}, 2));

    }


    /**
     * 二分查找+转换思路
     * 对于某一个开销 cost ，是否可以通过 maxOperations 操作得到
     */
    public static int minimumSize(int[] nums, int maxOperations) {
        // 可以不用排序，下面遍历计算操作数的时候，需要遍历全部
        Arrays.sort(nums);
        int left = 1, right = nums[nums.length - 1];
        int minCost = nums[nums.length - 1];

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (operate(nums, maxOperations, mid)) {
                minCost = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return minCost;
    }

    private static boolean operate(int[] nums, int maxOperations, int target) {
        for (int i = nums.length - 1; i >= 0 && nums[i] > target; i--) {
            maxOperations -= (nums[i] - 1) / target;
            if (maxOperations < 0) {
                return false;
            }
        }

        return maxOperations >= 0;
    }

}
